1. Technology Field
The invention relates to a decoding method, and more particularly, to a decoding method regarding a rewritable non-volatile memory module, a memory storage device and a memory controlling circuit unit using the same.
2. Description of Related Art
The markets of digital cameras, cellular phones, and MP3 players have expanded rapidly in recent years, resulting in escalated demand for storage media by consumers. The characteristics of data non-volatility, low power consumption, and compact size make the rewritable non-volatile memory module (e.g., flash memory) ideal for being built in the portable multi-media devices as cited above.
Generally, some error correcting codes (ECC) are added in data which are stored in the rewritable non-volatile memory module. In the past, the error correcting codes use more of algebraic decoding algorithms, such as (BCH code). However, probability decoding algorithms, such as low density parity code (LDPC), are gradually mature recently. The low density parity code is to use a sparse matrix to perform encoding and decoding. A null space of the sparse matrix contains all valid codewords. The number of correctable bits increases when the range between the valid codewords increases. However, the range between the valid codewords is not fixed, and so the number of correctable bits is not fixed. For example, when there are errors occurred to four bits in a codeword, the corresponding low density parity code can correct these errors; however, when there are errors occurred to other three bits in the same codeword, the corresponding low density parity code may not correct these errors. Furthermore, the capability of error correction of the low density parity code is not the same when different sparse matrices are used.
FIG. 1 is an error rate curve of the low density parity code.
Referring to FIG. 1, the horizontal axis represents a raw bit error rate (RBER), which refers to the error rate before data decoding; the vertical axis represents an uncorrectable bit error rate (UBER), which refers to the error rate after data decoding. Curve 180 represents the first matrix, and curve 190 represents the second matrix. The first matrix and the second matrix have the same size, that is, the codewords generated with these two matrices have the same code rate. However, elements in the first matrix and the second matrix are not the same. The curve 180 has a lower UBER within an error floor region, but the curve 190 has a lower UBER within a waterfall region. In other words, there exists a trade-off between the curve 180 and the curve 190. Accordingly, how to improve the capability of error correction under the condition of the same code rate is one of the major subjects for person skilled in the art.
Nothing herein should be construed as an admission of knowledge in the prior art of any portion of the present invention. Furthermore, citation or identification of any document in this application is not an admission that such document is available as prior art to the present invention, or that any reference forms a part of the common general knowledge in the art.